/**
 * Sizzle引擎
 */
(function(window, undefined) {

  var
      // 选择器缓存
      tokenCache = createCache(),
      compilerCache = createCache(),
      classCache = createCache(),

      booleans = "checked|selected|async|autofocus|autoplay|controls|defer|disabled|hidden|" +
          "ismap|loop|multiple|open|readonly|required|scoped",


      // 空白字符
      whitespace = "[\\x20\\t\\r\\n\\f]",

      // ClassName或ID Name
      identifier = "(?:\\\\[\\da-fA-F]{1,6}" + whitespace +
          "?|\\\\[^\\r\\n\\f]|[\\w-]|[^\0-\\x7f])+",

      // css选择器属性，如[type="phone"]
      attributes = "\\[" + whitespace + "*(" + identifier + ")(?:" + whitespace +

          // Operator (capture 2)
          "*([*^$|!~]?=)" + whitespace +

          // "Attribute values must be CSS identifiers [capture 5]
          // or strings [capture 3 or capture 4]"
          "*(?:'((?:\\\\.|[^\\\\'])*)'|\"((?:\\\\.|[^\\\\\"])*)\"|(" + identifier + "))|)" +
          whitespace + "*\\]",

      pseudos = ":(" + identifier + ")(?:\\((" +

          // To reduce the number of selectors needing tokenize in the preFilter, prefer arguments:
          // 1. quoted (capture 3; capture 4 or capture 5)
          "('((?:\\\\.|[^\\\\'])*)'|\"((?:\\\\.|[^\\\\\"])*)\")|" +

          // 2. simple (capture 6)
          "((?:\\\\.|[^\\\\()[\\]]|" + attributes + ")*)|" +

          // 3. anything else (capture 2)
          ".*" +
          ")\\)|)",

      // Leading and non-escaped trailing whitespace, capturing some non-whitespace characters preceding the latter
      rwhitespace = new RegExp( whitespace + "+", "g" ),

      // 去除左右空格用
      rtrim = new RegExp( "^" + whitespace + "+|((?:^|[^\\\\])(?:\\\\.)*)" +
          whitespace + "+$", "g" ),

      // 逗号
      rcomma = new RegExp( "^" + whitespace + "*," + whitespace + "*" ),

      // >, +, 空格, ~
      rcombinators = new RegExp( "^" + whitespace + "*([>+~]|" + whitespace + ")" + whitespace +
          "*" ),
      rdescend = new RegExp( whitespace + "|>" ),

      rpseudo = new RegExp( pseudos ),
      ridentifier = new RegExp( "^" + identifier + "$" ),

      matchExpr = {
          "ID": new RegExp( "^#(" + identifier + ")" ),
          "CLASS": new RegExp( "^\\.(" + identifier + ")" ),
          "TAG": new RegExp( "^(" + identifier + "|[*])" ),
          "ATTR": new RegExp( "^" + attributes ),
          "PSEUDO": new RegExp( "^" + pseudos ),
          "CHILD": new RegExp( "^:(only|first|last|nth|nth-last)-(child|of-type)(?:\\(" +
              whitespace + "*(even|odd|(([+-]|)(\\d*)n|)" + whitespace + "*(?:([+-]|)" +
              whitespace + "*(\\d+)|))" + whitespace + "*\\)|)", "i" ),
          "bool": new RegExp( "^(?:" + booleans + ")$", "i" ),

          // For use in libraries implementing .is()
          // We use this for POS matching in `select`
          "needsContext": new RegExp( "^" + whitespace +
              "*[>+~]|:(even|odd|eq|gt|lt|nth|first|last)(?:\\(" + whitespace +
              "*((?:-\\d)?\\d*)" + whitespace + "*\\)|)(?=[^-]|$)", "i" )
      },

      rhtml = /HTML$/i,
      rinputs = /^(?:input|select|textarea|button)$/i,
      rheader = /^h\d$/i,

      rnative = /^[^{]+\{\s*\[native \w/,

      // Easily-parseable/retrievable ID or TAG or CLASS selectors
      rquickExpr = /^(?:#([\w-]+)|(\w+)|\.([\w-]+))$/,

      rsibling = /[+~]/,

      // CSS escapes
      // http://www.w3.org/TR/CSS21/syndata.html#escaped-characters
      runescape = new RegExp( "\\\\[\\da-fA-F]{1,6}" + whitespace + "?|\\\\([^\\r\\n\\f])", "g" ),
      
      funescape = function( escape, nonHex ) {
          var high = "0x" + escape.slice( 1 ) - 0x10000;

          return nonHex ?

              // Strip the backslash prefix from a non-hex escape sequence
              nonHex :

              // Replace a hexadecimal escape sequence with the encoded Unicode code point
              // Support: IE <=11+
              // For values outside the Basic Multilingual Plane (BMP), manually construct a
              // surrogate pair
              high < 0 ?
                  String.fromCharCode( high + 0x10000 ) :
                  String.fromCharCode( high >> 10 | 0xD800, high & 0x3FF | 0xDC00 );
      };

  var Sizzle = function() {

  }

  Sizzle.tokenize = function (selector, parseOnly) {
      var matched,                        // 用于判断每执行一次while循环是否解析成功，如果为false说明css选择器有错误，直接终止循环
          match,                          // 正则匹配结果
          tokens,                         // Token序列
          soFar = selector,               // 表示字符串未解析的部分
          groups = [],                    // 存放已经解析好的Token序列
          preFilters = Expr.preFilter,    // 预处理用
          cached = tokenCache[selector];  // 缓存

      if (cached) {
          return parseOnly ? 0 : cached;
      }

      while (soFar) {

          // 第一大块，分组关系
          // 检查是否有逗号，有逗号的话就是多个Token序列
          // 比如像'div > p + .aaron[type="checkbox"], #id:first-child'这个选择器就是两个Token序列
          // groups = [
          //     [序列一],   // div > p + .aaron[type="checkbox"]
          //     [序列二]    // #id:first-child
          // ]
          if (!matched || (match = rcomma.exec(soFar))) {
              if (match) {
                  // 清除逗号
                  soFar = soFar.slice(match[0].length);
              }

              // 每有一个逗号，都要往groups压入一个Token序列
              // 然后就是最开始的时候也要往groups压入一个Token
              groups.push(tokens = []);
          }

          matched = false;

          // 第二大块，层级关系
          // 处理特殊的Token：>, +, 空格, ~
          if (match = rcombinators.exec(soFar)) {
              matched = match.shift();
              tokens.push({
                  value: matched,
                  type: match[0].replace(rtrim, " ")
              });

              // 处理完之后将其从待处理的字符中删除
              soFar = soFar.slice(matched.length);
          }

          // 第三大块，选择器
          // 这里开始分析这几种Token：TAG, ID, CLASS, ATTR, CHILD, PSEUDO, NAME
          // 如果通过正则匹配到了Token格式：match = matchExpr[ type ].exec( soFar )
          // 需要预处理的Token：ATTR, CHILD, PSEUDO
          // 交给预处理器处理：match = preFilters[ type ]( match )
          for (var type in Expr.filter) {
              if ( match = matchExpr[type].exec(soFar) ) {
                  // 预处理
                  if (preFilters[type]) {
                      match = preFilters[type](match);
                  }

                  matched = match.shift();
                  tokens.push({
                      value: matched,
                      type: type,
                      matches: match
                  })

                  // 处理完之后将其从待处理的字符中删除
                  soFar = soFar.slice(matched.length);
              }
          }

          // 如果到了这里都还没matched到，那么说明这个选择器在这里有错误
          // 直接中断词法分析过程
          // 这就是Sizzle对词法分析的异常处理
          if (!matched) {
              break;
          }
      }

      // 如果只需要这个接口检查选择器的合法性，直接就返回soFar的剩余长度，因为soFar长度大于零说明选择器不合法
      // 其余情况，如果soFar不等于""，抛出异常；否则把groups记录在cache里边并返回
      return parseOnly ?
          soFar.length :
          soFar ?
              Sizzle.error(selector) :

              // 这里对选择器(selector)做一个缓存
              tokenCache(selector, groups);
  }

  var Expr = Sizzle.selectors = {

      // 选择器缓存长度
      cacheLength: 50,

      // 查询seed集合用
      find: {

          "ID": function( id ) {
              var elem = document.getElementById( id );
              return elem ? [ elem ] : [];
          },

          "TAG": function( tag ) {
              return document.getElementsByTagName( tag );
          },

          "CLASS": function ( className ) {
              return document.getElementsByClassName( className );
          }
      },

      // 位置词素
      relative: {
          ">": { dir: "parentNode", first: true },
          " ": { dir: "parentNode" },
          "+": { dir: "previousSibling", first: true },
          "~": { dir: "previousSibling" }
      },

      // 预处理
      preFilter: {
          "ATTR": function( match ) {
              match[ 1 ] = match[ 1 ].replace( runescape, funescape );

              // Move the given value to match[3] whether quoted or unquoted
              match[ 3 ] = ( match[ 3 ] || match[ 4 ] ||
                  match[ 5 ] || "" ).replace( runescape, funescape );

              if ( match[ 2 ] === "~=" ) {
                  match[ 3 ] = " " + match[ 3 ] + " ";
              }

              return match.slice( 0, 4 );
          },

          "CHILD": function( match ) {

              /* matches from matchExpr["CHILD"]
                  1 type (only|nth|...)
                  2 what (child|of-type)
                  3 argument (even|odd|\d*|\d*n([+-]\d+)?|...)
                  4 xn-component of xn+y argument ([+-]?\d*n|)
                  5 sign of xn-component
                  6 x of xn-component
                  7 sign of y-component
                  8 y of y-component
              */
              match[ 1 ] = match[ 1 ].toLowerCase();

              if ( match[ 1 ].slice( 0, 3 ) === "nth" ) {

                  // nth-* requires argument
                  if ( !match[ 3 ] ) {
                      Sizzle.error( match[ 0 ] );
                  }

                  // numeric x and y parameters for Expr.filter.CHILD
                  // remember that false/true cast respectively to 0/1
                  match[ 4 ] = +( match[ 4 ] ?
                      match[ 5 ] + ( match[ 6 ] || 1 ) :
                      2 * ( match[ 3 ] === "even" || match[ 3 ] === "odd" ) );
                  match[ 5 ] = +( ( match[ 7 ] + match[ 8 ] ) || match[ 3 ] === "odd" );

                  // other types prohibit arguments
              } else if ( match[ 3 ] ) {
                  Sizzle.error( match[ 0 ] );
              }

              return match;
          },

          "PSEUDO": function( match ) {
              var excess,
                  unquoted = !match[ 6 ] && match[ 2 ];

              if ( matchExpr[ "CHILD" ].test( match[ 0 ] ) ) {
                  return null;
              }

              // Accept quoted arguments as-is
              if ( match[ 3 ] ) {
                  match[ 2 ] = match[ 4 ] || match[ 5 ] || "";

                  // Strip excess characters from unquoted arguments
              } else if ( unquoted && rpseudo.test( unquoted ) &&

                  // Get excess from tokenize (recursively)
                  ( excess = tokenize( unquoted, true ) ) &&

                  // advance to the next closing parenthesis
                  ( excess = unquoted.indexOf( ")", unquoted.length - excess ) - unquoted.length ) ) {

                  // excess is a negative index
                  match[ 0 ] = match[ 0 ].slice( 0, excess );
                  match[ 2 ] = unquoted.slice( 0, excess );
              }

              // Return only captures needed by the pseudo filter method (type and argument)
              return match.slice( 0, 3 );
          }
      },

      // 匹配器
      filter: {

          "TAG": function( nodeNameSelector ) {
              var nodeName = nodeNameSelector.replace( runescape, funescape ).toLowerCase();
              return nodeNameSelector === "*" ?
                  function() {
                      return true;
                  } :
                  function( elem ) {
                      return elem.nodeName && elem.nodeName.toLowerCase() === nodeName;
                  };
          },

          "CLASS": function( className ) {
              var pattern = classCache[ className + " " ];

              return pattern ||
                  ( pattern = new RegExp( "(^|" + whitespace +
                      ")" + className + "(" + whitespace + "|$)" ) ) && classCache(
                      className, function( elem ) {
                          return pattern.test(
                              typeof elem.className === "string" && elem.className ||
                              typeof elem.getAttribute !== "undefined" &&
                              elem.getAttribute( "class" ) ||
                              ""
                          );
                      } );
          },

          "ATTR": function( name, operator, check ) {
              return function( elem ) {
                  var result = Sizzle.attr( elem, name );

                  if ( result == null ) {
                      return operator === "!=";
                  }
                  if ( !operator ) {
                      return true;
                  }

                  result += "";

                  /* eslint-disable max-len */

                  return operator === "=" ? result === check :
                      operator === "!=" ? result !== check :
                          operator === "^=" ? check && result.indexOf( check ) === 0 :
                              operator === "*=" ? check && result.indexOf( check ) > -1 :
                                  operator === "$=" ? check && result.slice( -check.length ) === check :
                                      operator === "~=" ? ( " " + result.replace( rwhitespace, " " ) + " " ).indexOf( check ) > -1 :
                                          operator === "|=" ? result === check || result.slice( 0, check.length + 1 ) === check + "-" :
                                              false;
                  /* eslint-enable max-len */

              };
          },

          "CHILD": function( type, what, _argument, first, last ) {
              var simple = type.slice( 0, 3 ) !== "nth",
                  forward = type.slice( -4 ) !== "last",
                  ofType = what === "of-type";

              return first === 1 && last === 0 ?

                  // Shortcut for :nth-*(n)
                  function( elem ) {
                      return !!elem.parentNode;
                  } :

                  function( elem, _context, xml ) {
                      var cache, uniqueCache, outerCache, node, nodeIndex, start,
                          dir = simple !== forward ? "nextSibling" : "previousSibling",
                          parent = elem.parentNode,
                          name = ofType && elem.nodeName.toLowerCase(),
                          useCache = !xml && !ofType,
                          diff = false;

                      if ( parent ) {

                          // :(first|last|only)-(child|of-type)
                          if ( simple ) {
                              while ( dir ) {
                                  node = elem;
                                  while ( ( node = node[ dir ] ) ) {
                                      if ( ofType ?
                                          node.nodeName.toLowerCase() === name :
                                          node.nodeType === 1 ) {

                                          return false;
                                      }
                                  }

                                  // Reverse direction for :only-* (if we haven't yet done so)
                                  start = dir = type === "only" && !start && "nextSibling";
                              }
                              return true;
                          }

                          start = [ forward ? parent.firstChild : parent.lastChild ];

                          // non-xml :nth-child(...) stores cache data on `parent`
                          if ( forward && useCache ) {

                              // Seek `elem` from a previously-cached index

                              // ...in a gzip-friendly way
                              node = parent;
                              outerCache = node[ expando ] || ( node[ expando ] = {} );

                              // Support: IE <9 only
                              // Defend against cloned attroperties (jQuery gh-1709)
                              uniqueCache = outerCache[ node.uniqueID ] ||
                                  ( outerCache[ node.uniqueID ] = {} );

                              cache = uniqueCache[ type ] || [];
                              nodeIndex = cache[ 0 ] === dirruns && cache[ 1 ];
                              diff = nodeIndex && cache[ 2 ];
                              node = nodeIndex && parent.childNodes[ nodeIndex ];

                              while ( ( node = ++nodeIndex && node && node[ dir ] ||

                                  // Fallback to seeking `elem` from the start
                                  ( diff = nodeIndex = 0 ) || start.pop() ) ) {

                                  // When found, cache indexes on `parent` and break
                                  if ( node.nodeType === 1 && ++diff && node === elem ) {
                                      uniqueCache[ type ] = [ dirruns, nodeIndex, diff ];
                                      break;
                                  }
                              }

                          } else {

                              // Use previously-cached element index if available
                              if ( useCache ) {

                                  // ...in a gzip-friendly way
                                  node = elem;
                                  outerCache = node[ expando ] || ( node[ expando ] = {} );

                                  // Support: IE <9 only
                                  // Defend against cloned attroperties (jQuery gh-1709)
                                  uniqueCache = outerCache[ node.uniqueID ] ||
                                      ( outerCache[ node.uniqueID ] = {} );

                                  cache = uniqueCache[ type ] || [];
                                  nodeIndex = cache[ 0 ] === dirruns && cache[ 1 ];
                                  diff = nodeIndex;
                              }

                              // xml :nth-child(...)
                              // or :nth-last-child(...) or :nth(-last)?-of-type(...)
                              if ( diff === false ) {

                                  // Use the same loop as above to seek `elem` from the start
                                  while ( ( node = ++nodeIndex && node && node[ dir ] ||
                                      ( diff = nodeIndex = 0 ) || start.pop() ) ) {

                                      if ( ( ofType ?
                                          node.nodeName.toLowerCase() === name :
                                          node.nodeType === 1 ) &&
                                          ++diff ) {

                                          // Cache the index of each encountered element
                                          if ( useCache ) {
                                              outerCache = node[ expando ] ||
                                                  ( node[ expando ] = {} );

                                              // Support: IE <9 only
                                              // Defend against cloned attroperties (jQuery gh-1709)
                                              uniqueCache = outerCache[ node.uniqueID ] ||
                                                  ( outerCache[ node.uniqueID ] = {} );

                                              uniqueCache[ type ] = [ dirruns, diff ];
                                          }

                                          if ( node === elem ) {
                                              break;
                                          }
                                      }
                                  }
                              }
                          }

                          // Incorporate the offset, then check against cycle size
                          diff -= last;
                          return diff === first || ( diff % first === 0 && diff / first >= 0 );
                      }
                  };
          },

          "PSEUDO": function( pseudo, argument ) {

              // pseudo-class names are case-insensitive
              // http://www.w3.org/TR/selectors/#pseudo-classes
              // Prioritize by case sensitivity in case custom pseudos are added with uppercase letters
              // Remember that setFilters inherits from pseudos
              var args,
                  fn = Expr.pseudos[ pseudo ] || Expr.setFilters[ pseudo.toLowerCase() ] ||
                      Sizzle.error( "unsupported pseudo: " + pseudo );

              // The user may use createPseudo to indicate that
              // arguments are needed to create the filter function
              // just as Sizzle does
              if ( fn[ expando ] ) {
                  return fn( argument );
              }

              // But maintain support for old signatures
              if ( fn.length > 1 ) {
                  args = [ pseudo, pseudo, "", argument ];
                  return Expr.setFilters.hasOwnProperty( pseudo.toLowerCase() ) ?
                      markFunction( function( seed, matches ) {
                          var idx,
                              matched = fn( seed, argument ),
                              i = matched.length;
                          while ( i-- ) {
                              idx = indexOf( seed, matched[ i ] );
                              seed[ idx ] = !( matches[ idx ] = matched[ i ] );
                          }
                      } ) :
                      function( elem ) {
                          return fn( elem, 0, args );
                      };
              }

              return fn;
          },

          "ID": function( id ) {
              var attrId = id.replace( runescape, funescape );
              return function( elem ) {
                  return elem.getAttribute( "id" ) === attrId;
              };

          }
      },
  }

  // 异常
  Sizzle.error = function( msg ) {
      throw new Error( "Syntax error, unrecognized expression: " + msg );
  }

  // 选择器缓存
  function createCache() {
      var keys = [];

      function cache(key, value) {
          if (keys.push(key) > Expr.cacheLength) {
              delete cache[keys.shift()];
          }
          return (cache[key] = value);
      }
      return cache;
  }

  Sizzle.select = function(selector) {
      var
          i,              // 计数器
          tokens,         // token序列
          token,          // token
          type,           // token类型：TAG, ID, CLASS, ATTR, CHILD, PSEUDO, NAME, 层级关系(>, +, 空格, ~)
          find,           // seed集合查询方法：getElementById、getElementsByTagName、getElementsByClassName
          seed,           // 种子集合：类型为ID、TAG、CLASS中任意一种的DOM元素集合
          match,          // 词法解析后的数据
          results = []    // 目标元素
          ;

      // 词法解析
      match = Sizzle.tokenize(selector);

      // 只有一组tokens的情况
      // 筛选出种子合集(seed)，重组css选择器
      if (match.length === 1) {
          tokens = match[0];
          i = tokens.length;

          // 通过遍历找出seed集合，顺序是从右往左
          while (i--) {
              token = tokens[i];

              // 如果是层级关系(>, +, 空格, ~)，跳出循环
              if (Expr.relative[(type = token.type)]) {
                  break;
              }

              // 如果是ID、TAG、CLASS中的一种
              if (find = Expr.find[type]) {
                  // 找到目标DOM元素
                  if (seed = find(token.matches[0])) {
                      // 从tokens中删除
                      tokens.splice(i, 1);
                      // 重组选择器
                      selector = seed.length && toSelector(tokens);
                      break;
                  }
              }
          }
      }

      var superMatcher = Sizzle.compile(selector, match);
      superMatcher(seed, results);

      return results;
  }

  // Token序列转css选择器字符串
  function toSelector( tokens ) {
      var i = 0,
          len = tokens.length,
          selector = "";
      for ( ; i < len; i++ ) {
          selector += tokens[ i ].value;
      }
      return selector;
  }

  // 预编译
  Sizzle.compile = function(selector, match) {
      var
          i,
          elementMatchers = [],
          cached = compilerCache[selector];

      if (!cached) {
          // match一般是有值的，所以这行if语句基本上是个摆设
          if (!match) {
              match = Sizzle.tokenize(selector);
          }

          i = match.length;
          while(i--) {
              cached = matcherFromTokens(match[i]);
              elementMatchers.push(cached);
          }
      }

      cached = compilerCache(
          selector,
          matcherFromGroupMatchers(elementMatchers)
      )

      return cached;
  }

  // 遍历Token序列生成匹配器
  function matcherFromTokens(tokens) {
      var
          i,
          token,
          matcher,
          matchers = []
          ;

      for (i = 0; i < tokens.length; i++) {
          token = tokens[i];

          if (matcher = Expr.relative[token.type]) { // 生成层级匹配器
              matchers = [addCombinator(elementMatcher(matchers), matcher)];
          } else {
              // 问题：为什么这里不写成matcher = Expr.filter[token.type](token.matches);
              // 因为ATTR类型的匹配器需要传入三个参数
              matcher = Expr.filter[token.type].apply(null, token.matches);
              matchers.push(matcher);
          }
      }

      return elementMatcher(matchers);
  }

  // 超级匹配器（多组）
  // 像div > p + .aaron[type="checkbox"], #id:first-child这种选择器有两组matcherFromTokens匹配器
  // 该方法的作用就是将两组matcherFromTokens匹配器合并成一个匹配器
  function matcherFromGroupMatchers(elementMatchers) {
      return function (seed, results) {
          var i,
              j,
              elems,      // 种子合集
              elem,       // 种子合集中的单个DOM元素
              matcher;    // matcherFromTokens匹配器

          // 如果没有种子元素则全文检索
          elems = seed || Expr.find["TAG"]("*");

          // 遍历所有元素
          for (i = 0; i < elems.length; i++) {
              j = 0;
              elem = elems[i];

              // 遍历所有matcherFromTokens匹配器
              // 把elems中的元素挨个放入elementMatchers匹配器中
              // 若返回为true，将该元素放入results集合中
              while (matcher = elementMatchers[j++]) {
                  if (matcher(elem)) {
                      results.push(elem);
                  }
              }
          }
      }
  }

  // 合并多个匹配器
  function elementMatcher( matchers ) {
      return matchers.length > 1 ?

          // 如果是多个匹配器
          function( elem, context, xml ) {
              var i = matchers.length;
              while ( i-- ) {
                  if ( !matchers[ i ]( elem, context, xml ) ) {
                      return false;
                  }
              }
              return true;
          } :

          // 如果是单个匹配器，返回自己即可
          matchers[ 0 ];
  }

  // 层级关系处理器
  function addCombinator(matcher, combinator) {
      var dir = combinator.dir;

      return combinator.first ?

          // 紧密型
          function( elem, context, xml ) {
              while ( ( elem = elem[ dir ] ) ) {

                  // 加这么一个判断是因为有的时候拿到的是text类型的元素
                  if ( elem.nodeType === 1 ) {
                      return matcher( elem, context, xml );
                  }
              }
              return false;
          } :

          // 非紧密型一直递归查询，查到最后为null会跳出循环并且返回false
          // 如果递归过程中某一层返回true
          function( elem, context, xml ) {
              while ( ( elem = elem[ dir ] ) ) {
                  if ( elem.nodeType === 1 ) {
                      if (matcher(elem, context, xml)) {
                          return true;
                      }
                  }
              }
              return false;
          }
  }

  // 获取元素属性值
  Sizzle.attr = function( elem, name ) {
      return elem.getAttribute( name );
  }

  window.Sizzle = Sizzle;
})(window);